package dynamicprogramming.最长回文子串;

public class Solution {
    public String longestPalindrome(String s) {
        /**
         * babad
         * f[i][j] 表示 字符串从i到j是否是回文
         * 动态转移方程 ： f[i][j] =  s[i] == [j] && f[i+1][j-1]
         * 初始化数组：单个字符时肯定是回文
         */
        int n = s.length();
        boolean[][] f = new boolean[n][n];
        String ans = "";
        //长度为1
        for (int i = 0; i < n; i++) {
            f[i][i] = true;
            ans = s.substring(i, i + 1);
        }
        //长度为2
        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                f[i][i + 1] = true;
                ans = s.substring(i, i + 2);
            }
        }
        //长度大于3
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i + len <= n; i++) {
                int j = i + len - 1;
                f[i][j] = s.charAt(i) == s.charAt(j) && f[i + 1][j - 1];
                if (f[i][j] && ans.length() < len) {
                    ans = s.substring(i, j + 1);
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.longestPalindrome("ccc"));
    }
}
